package cn.cxq.learning.recursion;


import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 走迷宫问题，算最少步数
 * 0代表没走过，1代表墙，2代表走过，3代表死路
 */
public class Maze {

    private int[][] map; //地图
    private int[][] plan; //策略（走上下左右的顺序）

    private int stap;

    public Maze(int[][] plan) {

        this.map = new int[8][8]; //迷宫结构
        this.plan = plan;
        this.stap = -1;

        for (int i = 0; i < map.length; i++) {
            map[i][0] = 1;
            map[i][7] = 1;
        }

        for (int i = 0; i < map[0].length; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }

        map[3][1] = 1;
        map[3][2] = 1;
    }

    public int getStap() {
        return stap;
    }

    public void showMap(){
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
    }

    public boolean go(int i,int j){
        if (map[6][6] == 2){
            return true;
        }else {
            if (map[i][j] == 0) {
                map[i][j] = 2;
                for (int k = 0; k < plan.length; k++) {
                    if (go(i + plan[k][0],j + plan[k][1])) {
                        stap ++;
                        return true;
                    }
                }
                    map[i][j] = 3;
                    return false;

            }else return false; //取了值的要么是走过的2，要么是墙1，要么是死路3。
        }
    }

    /**
     * 获取所有的策略
     * @return
     */
    public static List<int[][]> generateGoPlan(){

        ArrayList<int[][]> goPlans = new ArrayList<>();

        int[][] direction = {{1,0},{0,1},{-1,0},{0,-1}};

        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                for (int k = 0; k < 4; k++) {
                    for (int l = 0; l < 4; l++) {

                        //使用一个set，通过set的长度来判断四个整数是否重复
                        Set<Integer> integers = new HashSet<>();
                        integers.add(i);
                        integers.add(j);
                        integers.add(k);
                        integers.add(l);

                        if (integers.size() == 4) {

                            int[][] plan = new int[4][2];

                            plan[0][0] = direction[i][0];
                            plan[0][1] = direction[i][1];

                            plan[1][0] = direction[j][0];
                            plan[1][1] = direction[j][1];

                            plan[2][0] = direction[k][0];
                            plan[2][1] = direction[k][1];

                            plan[3][0] = direction[l][0];
                            plan[3][1] = direction[l][1];

                            goPlans.add(plan);

                        }

                    }
                }
            }
        }

        return goPlans;
    }
}
